The Global Positioning System (GPS) is a satellite-based location system. In the GPS, several satellites orbiting the earth provide signal codes that are detected by receivers. The receivers use the codes to lock onto the satellite signal. The receiver or user then measures the time of arrival of the satellite signal against an internal clock, which indicates a delay from the satellite. Such delay is determined for at least four different satellites. Those delays translate to distances. Because the distances to each of four satellites are known, and because the position of the satellites are known, the X, Y, and Z coordinates of the user may be calculated, as well as the user's clock error. This method is known as pseudo-ranging, and systems other than GPS use similar technology.
The delay between transmission of a satellite and reception by a receiver is obtained by causing the receiver to latch onto a repetitive code of a particular satellite. To this end, the receiver generates the code of each satellite in a repetitive pattern and then, for a particular satellite, tries to line up the internally generated code with the received code from the satellite. To “line up” the internally generated code, the internally generated code sequence must be delayed by some amount. This delay provides the time measurement from the internal clock, Codesat1(t)=Coderec(t+δ1), where δ1 is a delay value. By aligning internal codes of other satellites with corresponding internal codes, other delay values may be obtained. Thus, for three other satellites, delay values δ2, δ3, and δ4 may be generated. Then, by obtaining the position information for those satellites (xj, yj, zj) for j={1, 2, 3, 4}, a system of equations may be set up to determine the location of the receiving device.
The system of equations is derived from the equation for the distance between a satellite and the receiver in terms of delay, which may be expressed as: Distance=δj*C (speed of light). However, the measured delay does not provide an absolute delay value because the clock in the receiver is not necessarily synchronized to the satellites, which are synchronized together. So the actual distance between a satellite n and the receiver is the measured delay δj, plus a receiver clock offset Toff, times the speed of light. Thus, the following system of equations can be set up:(δ1+Toff)*C=[(x1−xr)2+(y1−yr)2+(z1−zr)2]1/2 (δ2+Toff)*C=[(x2−xr)2+(y2−yr)2+(z2−zr)2]1/2 (δ3+Toff)*C=[(x3−xr)2+(y3−yr)2+(z3−zr)2]1/2 (δ4+Toff)*C=[(x4−xr)2+(y4−yr)2+(z4−zr)2]1/2 
The above four equations amount to four equations with four unknown variables, which may then be solved for the receiver position xr, yr, zr, as well as the offset of the receiver clock Toff. Because the speed of light is 286,000 miles per second, even a small discrepancy in a delay measurement δj that is used to compute the distance from the distance equation already noted, can result in significant inaccuracy.
The processing capability of wireless devices is increasing and the incorporation of GPS positioning applications in such devices is desirable. Such applications may work well in these devices in environments where a strong signal may be received from a satellite. These devices, however, are typically used in urban environments. In an urban environment, the user may travel under a bridge, through a tunnel, or through what is referred to in the literature as an “urban canyon,” in which buildings block the signals or reflect them. Consequently, the wireless device may need to acquire and track weak signals from the positioning satellites.
Accurate alignment of the internal and external codes to get a precise delay number in a weak signal environment may be difficult. To facilitate accurate alignment, the acquisition code sequence, known in the art at the C/A code, is 1023 bits and repeated periodically every 1 millisecond. By superimposing the internal code over the received code for multiple instances of the code, a correlation technique may be used to filter out noise present in the signal. As the number of 1 millisecond periods used for correlation increases, the ability of the receiver to acquire weaker signals increases.
The practical number of subsequent sequences of the C/A code that may be used is hindered, however, by the fact that the C/A code is in fact superimposed over another signal, referred to as the data signal, which has a pulse width of 20 milliseconds. The data signal contains the time and location information for the satellite, among other things. Before the signal is acquired, the data signal is unknown to the receiver, and appears as a pseudorandom signal. Because the receiver does not know the data signal, the receiver does not know the effects of the data signal on the C/A sequences. Changes in the data signal from a +1 to a −1 value completely change the appearance of the C/A sequences. Moreover, although there are 20 repetitions of the C/A sequence for every data signal value, the receiver does not have a priori knowledge of when the transitions of the data signal occur. Accordingly, the imposition of the data signal makes the use of multiple C/A sequences to achieve acquisition of the C/A code for weak GPS signals difficult.
One way of improving the sensitivity to weak signals of a GPS receiver is to increase the pre-detection integration time (PIT), which reduces the noise bandwidth. The improvement available through this technique is limited because the location of the data bits and bit edges in the signal is unknown. For a GPS C/A code, the upper bound on the PIT is one code length (1 ms), if the data bits and the bit edge positions are unknown. The upper bound is one data length (20 ms), if only the data bits are unknown. Increasing the PIT, however, requires an increased number of Doppler bins, a signal processing structure used to estimate the Doppler shift in a signal. The increase in the number of these structures increases the processing and memory requirements for the coherent integrations.
Conventional weak signal acquisition systems implemented in hardware search satellites at each possible code delay and Doppler shift in a sequential manner. As a result, the processing time and memory requirements increase as the size of the search space increases. One approach to reducing the computational demands for coherent integrations is to use circular correlation techniques implemented in software. Circular correlation uses Fast Fourier Transform (FFT) methods to calculate the coherent integration at all possible code delays for each possible Doppler shift. Some systems that use other approaches than circular correlation are able to eliminate the use of Doppler bins, but they suffer from low sensitivity. Other systems use circular correlation with increased PIT, but they do not address unknown bit edge positions and data bits.
Another approach to reducing the demand for computational resources is to use a Double Block Zero Padding (DBZP) approach. This approach calculates correlations at all possible code delays and Doppler shifts in the same processing steps. The maximum integration length that can be used with DBZP is limited, however. The limitation arises from the use of only one replica code that is not compensated by the effect of the Doppler shift on the code duration.
These known techniques for acquiring the C/A code for weak signals require long coherent and incoherent integrations. These acquisition techniques also require more processing capability or memory than is typically available in many wireless devices. In order to improve the ability of wireless devices to incorporate GPS applications, weak signal acquisition methods are needed that do not require more computational resources than those available in wireless devices.
The discussion above focuses on the detection and acquisition of weak signals in the presence of background noise. That is, the data signal has been attenuated to a level that makes its detection difficult even when no interfering signal is present. A different problem arises when the GPS receiver attempts to detect and acquire a signal in the presence of strong interfering signals. As noted above, the GPS signal includes a C/A code for identification. Different C/A codes have non-zero cross-correlation. The cross-correlation between the local replica code and the code of a received interfering signal causes the interfering signal to appear with a reduced power from its original received power. This causes the interfering signal to appear at many code delays, which affects the processing for detecting and acquiring the GPS signal in the presence of a strong interfering signal.
In response to the above noted needs, a method of signal acquisition has been developed that is useful with weak signals. This method is disclosed in co-pending U.S. patent application Ser. No. 11/212,125, which was filed on Aug. 25, 2005 and is entitled “System and Method For Acquiring Weak Signals In A Global Positioning Satellite System.” The method set forth in that application uses circular correlation and double block zero padding to perform the coherent and incoherent integrations required for signal acquisition. Those methods, however, remain relatively resource intensive. Computational efficiencies in the performance of the method disclosed in that application would increase the range of devices in which the method may be used.